In [1]:
import sys
#!{sys.executable} -m pip install 
#!conda install --yes --prefix {sys.prefix} 
sys.path.append('../')
from ISI import Problem, Solution, excel_to_pb, Meta_param, Matheuristic
import numpy as np
from copy import deepcopy

Building problems

In [2]:
path = '../Data/Burundi final v2.xlsx'
schools, warehouses, Q1, V_number, makes = excel_to_pb(path)
problem_global = Problem(warehouses, schools, Q1, V_number=V_number, makes=makes, T=2, H=1, time_step=0.5)
problem_global.time_fuse()
In [3]:
problems = problem_global.clustering()

Found 3 clusters!
In [4]:
problemBUJUMBURA,problemNGOZI,problemGITEGA = problems[0], problems[1], problems[2]
In [5]:
param = Meta_param(seed = 1)

Cluster of NGOZI

In [6]:
problem = problemNGOZI

Default parameters

In [7]:
problem1 = problem.copy()
problem1
Out[7]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'NGOZI'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 9 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [8]:
param
Out[8]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [9]:
heuristic1 = Matheuristic(problem1,param)
heuristic1.algo2()

 Total algorithm time = 744.05 
Total ISI running times : 
  Define problem  :  149.16
  Solve problem   :  580.72
  Compute TSPs  :  4.45
  Visualisation  :  0.19
In [10]:
heuristic1.plot_steps()
In [11]:
heuristic1.solution_best
Out[11]:
Solution with a total cost of 31.919  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  1.7326

With double number of vehicules

In [12]:
problem2 = problem.copy()
problem2.augment_v(2)
problem2
Out[12]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'NGOZI'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 18 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [13]:
param
Out[13]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [14]:
heuristic2 = Matheuristic(problem2,param)
heuristic2.algo2()

 Total algorithm time = 650.31 
Total ISI running times : 
  Define problem  :  408.56
  Solve problem   :  211.05
  Compute TSPs  :  4.56
  Visualisation  :  0.23
In [15]:
heuristic2.plot_steps()
In [16]:
heuristic2.solution_best
Out[16]:
Solution with a total cost of 32.867  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  1.7841

Without time splitting

In [17]:
problem3 = problem.copy()
problem3.H = 2
problem3
Out[17]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'NGOZI'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 9 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [18]:
param
Out[18]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [19]:
heuristic3 = Matheuristic(problem3,param)
heuristic3.algo2()

 Total algorithm time = 339.36 
Total ISI running times : 
  Define problem  :  159.22
  Solve problem   :  164.09
  Compute TSPs  :  4.67
  Visualisation  :  0.21
In [20]:
heuristic3.plot_steps()
In [21]:
heuristic3.solution_best
Out[21]:
Solution with a total cost of 36.604  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  1.7563

Without virtual time step

In [22]:
problem4 = problem.copy()
problem4.t_virt = 0
problem4.time_fuse(1/problem.t_virt)
problem4
Out[22]:
Parameters of the problem : 
         Number of time steps : 2 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'NGOZI'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 9 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 2 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 1 
         Number of virtual time steps between segments : 0 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0
In [23]:
param
Out[23]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [24]:
heuristic4 = Matheuristic(problem4,param)
heuristic4.algo2()

 Total algorithm time = 91.13 
Total ISI running times : 
  Define problem  :  37.71
  Solve problem   :  44.72
  Compute TSPs  :  5.67
  Visualisation  :  0.13
In [25]:
heuristic4.plot_steps()
In [26]:
heuristic4.solution_best
Out[26]:
Solution with a total cost of 34.655  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  2.1923

With higher rho

In [27]:
problem5 = problem.copy()
problem5
Out[27]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'NGOZI'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 9 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [28]:
param5 = deepcopy(param)
param5.rho_percent = 0.6
In [29]:
heuristic5 = Matheuristic(problem5,param5)
heuristic5.algo2()

 Total algorithm time = 340.71 
Total ISI running times : 
  Define problem  :  161.11
  Solve problem   :  163.79
  Compute TSPs  :  4.91
  Visualisation  :  0.24
In [30]:
heuristic5.plot_steps()
In [31]:
heuristic5.solution_best
Out[31]:
Solution with a total cost of 31.769  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  2.1426

With lower rho

In [32]:
problem6 = problem.copy()
problem6
Out[32]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'NGOZI'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 9 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [33]:
param6 = deepcopy(param)
param6.rho_percent = 0.1
In [34]:
heuristic6 = Matheuristic(problem6,param6)
heuristic6.algo2()

 Total algorithm time = 257.71 
Total ISI running times : 
  Define problem  :  135.36
  Solve problem   :  110.14
  Compute TSPs  :  3.59
  Visualisation  :  0.18
In [35]:
heuristic6.plot_steps()
In [36]:
heuristic6.solution_best
Out[36]:
Solution with a total cost of 35.839  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  2.076

Cluster of GITEGA

In [37]:
problem = problemGITEGA

Default parameters

In [38]:
problem1 = problem.copy()
problem1
Out[38]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'GITEGA'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 8 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [39]:
param
Out[39]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [40]:
heuristic1 = Matheuristic(problem1,param)
heuristic1.algo2()

 Total algorithm time = 268.04 
Total ISI running times : 
  Define problem  :  153.87
  Solve problem   :  100.72
  Compute TSPs  :  4.89
  Visualisation  :  0.2
In [41]:
heuristic1.plot_steps()
In [42]:
heuristic1.solution_best
Out[42]:
Solution with a total cost of 32.517  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  1.9871

With double number of vehicules

In [43]:
problem2 = problem.copy()
problem2.augment_v(2)
problem2
Out[43]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'GITEGA'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 16 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [44]:
param
Out[44]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [45]:
heuristic2 = Matheuristic(problem2,param)
heuristic2.algo2()

 Total algorithm time = 664.29 
Total ISI running times : 
  Define problem  :  430.5
  Solve problem   :  203.33
  Compute TSPs  :  5.94
  Visualisation  :  0.28
In [46]:
heuristic2.plot_steps()
In [47]:
heuristic2.solution_best
Out[47]:
Solution with a total cost of 33.768  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  1.9362

Without time splitting

In [48]:
problem3 = problem.copy()
problem3.H = 2
problem3
Out[48]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'GITEGA'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 8 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [49]:
param
Out[49]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [50]:
heuristic3 = Matheuristic(problem3,param)
heuristic3.algo2()

 Total algorithm time = 214.4 
Total ISI running times : 
  Define problem  :  117.48
  Solve problem   :  85.2
  Compute TSPs  :  4.36
  Visualisation  :  0.17
In [51]:
heuristic3.plot_steps()
In [52]:
heuristic3.solution_best
Out[52]:
Solution with a total cost of 32.808  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  2.922

Without virtual time step

In [53]:
problem4 = problem.copy()
problem4.t_virt = 0
problem4.time_fuse(1/problem.t_virt)
problem4
Out[53]:
Parameters of the problem : 
         Number of time steps : 2 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'GITEGA'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 8 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 2 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 1 
         Number of virtual time steps between segments : 0 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0
In [54]:
param
Out[54]:
 Meta parameters of the heurestics : 
 
 For iterations : 
     Length of segments (delta) : 10 , 
     Tau (the temperature) begins at 3.0, finishes at 0.1 and is cooled by 0.9 --> 32 steps 
  
 Inside algorithm's parameters : 
     Bounds of epsilon  : (0.05, 0.15) , 
     For randomizing G (ksi) : 0.142 
 
     Operators' parameters : 
     Sigmas for updating the weigths of the operators (10, 5, 2), with reaction factor : 0.8 , 
     Percentage rho for operators : 0.3 , 
     Solver used for the MIP : CBC
In [55]:
heuristic4 = Matheuristic(problem4,param)
heuristic4.algo2()

 Total algorithm time = 105.76 
Total ISI running times : 
  Define problem  :  35.45
  Solve problem   :  60.33
  Compute TSPs  :  6.53
  Visualisation  :  0.15
In [56]:
heuristic4.plot_steps()
In [57]:
heuristic4.solution_best
Out[57]:
Solution with a total cost of 40.805  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  2.8161

With higher rho

In [58]:
problem5 = problem.copy()
problem5
Out[58]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'GITEGA'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 8 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [59]:
param5 = deepcopy(param)
param5.rho_percent = 0.6
In [60]:
heuristic5 = Matheuristic(problem5,param5)
heuristic5.algo2()

Duration constraint looks infeasible
Duration constraint looks infeasible
Duration constraint looks infeasible
Duration constraint looks infeasible
Duration constraint looks infeasible
 Total algorithm time = 249.7 
Total ISI running times : 
  Define problem  :  135.11
  Solve problem   :  100.37
  Compute TSPs  :  5.91
  Visualisation  :  0.21
In [61]:
heuristic5.plot_steps()
In [62]:
heuristic5.solution_best
Out[62]:
Solution with a total cost of 29.137  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  2.1999

With lower rho

In [63]:
problem6 = problem.copy()
problem6
Out[63]:
Parameters of the problem : 
         Number of time steps : 4 
         Number of schools : 50 
         Number of warehouses : 2 
          Name of the warehouses : ['BUJUMBURA', 'GITEGA'] 
   Parameters specific to transportation : 
         Number of vehicles in total : 8 
         Cost per kilometers done : 10.0 
         Capacity of trucks for pickups : 20 
         Capacity of trucks are from  : 18.0  to 20  
   Parameters specific to time steps : 
         Number of time steps : 4 
         Length of a time step (in weeks) : 0.5 
         Length of time horizon segment for optimization (H) : 2 
         Number of virtual time steps between segments : 0.5 
  Duration constraint : 
         Maximum time spending in a tour : 10 
         Loading time at each school : 0.5 
         Speed of vehicules : 40 
         Number of virtual time steps between segments : 0.5
In [64]:
param6 = deepcopy(param)
param6.rho_percent = 0.1
In [65]:
heuristic6 = Matheuristic(problem6,param6)
heuristic6.algo2()

Duration constraint looks infeasible
 Total algorithm time = 229.54 
Total ISI running times : 
  Define problem  :  131.77
  Solve problem   :  83.9
  Compute TSPs  :  5.63
  Visualisation  :  0.2
In [66]:
heuristic6.plot_steps()
In [67]:
heuristic6.solution_best
Out[67]:
Solution with a total cost of 59.334  
 Constraints fulfilled : 
  Truck constraint  :  True
  Duration constraint  :  True
  I_s constraint  :  True
  I_w constraint  :  True
  
 Running time : 
  visualisation  :  2.8069